package _220325;

import java.util.Scanner;

/**
 * @author ShadowLim
 * @create 2022-03-25-9:45
 */
public class 分考场 {
    /**
     * https://www.cnblogs.com/blzm742624643/p/10383905.html
     */
    static int res = 1061109567;    // 100 也可以（似乎更快 173ms）(1061109567 :203ms)
    static int n, m;
    static int[][] graph;   // 是否认识 认识为 1 不认识为0
    static int[][] cun;     // 第一维度：考场编号 第二维度：当前考场里面的学生
                            // cun[1][1] = 2, cun[1][2] = 0;表示考场 1 里面第一个存在的人是 2，然后后面一位是 0，
                            // 也就是不存在人了,那么这时的cun[1] = 1;表示的是考场编号1里面人的数量为1
    static int[] count;    // 记录cun数组中房间编号对应的的学生的数量

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        count = new int[105];
        graph = new int[105][105];
        cun = new int[105][105];
        while (m-- >0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph[a][b] = 1;
            graph[b][a] = 1;
        }
        scanner.close();

        dfs(1, 0);
        System.out.println(res);
    }

    /**
     * 考虑编号为 k 的学生
     * @param k
     */
    private static void dfs(int k, int num) {
        if (num >= res) {    // 剪枝 num : 当前方案所需的房间数量
            return;
        }
        if (k > n) {    // 所有学生安排完毕
            res = Math.min(res, num);
            return;
        }
        boolean flag = false;
        // 遍历当前已分配的房间，贪心的加入到已分配的房间(查看是否可以加入)
        for (int i = 1; i <= num; i++) {
            int size = count[i];    // 房间编号为 i 的学生人数
            int jishu = 0;  // 得到和当前学生不认识的人数
            for (int j = 1; j <= size; j++) {
                if (graph[k][cun[i][j]] == 0) { // 不认识
                    jishu++;
                }
            }
            if (jishu == size) {
                cun[i][++count[i]] = k; //如果这里面的学生都和现在遍历的都不认识 就加入编号为 k 的学生
                dfs(k + 1, num);
                count[i]--; // 回溯
            }
        }
        // 无法加入当前已分配的房间 则重新开一个房间
        cun[num + 1][++count[num + 1]] = k; // 把编号为 k 的学生放入编号为 num + 1 的房间
        dfs(k + 1, num + 1);
        --count[num + 1];   // 回溯
    }
}
